import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:${USER}
 * Date:${YEAR}-${MONTH}-${DAY}
 * ${TIME}
 */
public class Main {
    public static void main(String[] args) {
        String[] bank = {"AACCGGTA"};
        int i=minMutation( "AACCGGTT","AACCGGTA",bank);
        System.out.println(i);
    }

    static char[] c={'A','C','G','T'};
    public static int minMutation(String startGene, String endGene, String[] bank) {
        Queue<String> queue=new LinkedList<>();
        HashSet<String> hashSet=new HashSet<>();
        HashSet<String> setBank=new HashSet<>();
        for (int i = 0; i < bank.length; i++) {
            setBank.add(bank[i]);
        }
        queue.add(startGene);

        hashSet.add(startGene);
        if(startGene.equals(endGene))return 0;
        if(!setBank.contains(endGene))return -1;
        int step=0;
        while (!queue.isEmpty()){
            step++;//应该是这里往扩一次才是最短
            int size= queue.size();
            for (int i=0;i<size;i++){
                String ret=queue.poll();
                for (int j = 0; j <8; j++) {

                    char[] retCh=ret.toCharArray();
                    for (int k = 0; k < 4; k++) {
                        retCh[j]=c[k];
                        String newRet=new String(retCh);
                        if(!hashSet.contains(newRet)&& setBank.contains(newRet)){
                            queue.add(newRet);
                            hashSet.add(newRet);
                            //step++这里++是错误的，
                            if(newRet.equals(endGene))return step;
                        }

                    }
                }
            }
        }
        return -1;
    }
}